// 冬季已经来临。 你的任务是设计一个有固定加热半径的供暖器向所有房屋供暖。

// 现在，给出位于一条水平线上的房屋和供暖器的位置，找到可以覆盖所有房屋的最小加热半径。

// 所以，你的输入将会是房屋和供暖器的位置。你将输出供暖器的最小加热半径。

// 说明:

// 给出的房屋和供暖器的数目是非负数且不会超过 25000。
// 给出的房屋和供暖器的位置均是非负数且不会超过10^9。
// 只要房屋位于供暖器的半径内(包括在边缘上)，它就可以得到供暖。
// 所有供暖器都遵循你的半径标准，加热的半径也一样。
// 示例 1:

// 输入: [1,2,3],[2]
// 输出: 1
// 解释: 仅在位置2上有一个供暖器。如果我们将加热半径设为1，那么所有房屋就都能得到供暖。
// 示例 2:

// 输入: [1,2,3,4],[1,4]
// 输出: 1
// 解释: 在位置1, 4上有两个供暖器。我们需要将加热半径设为1，这样所有房屋就都能得到供暖。

#include <vector>
#include <algorithm>

using std::vector;
using std::sort;
using std::max;

class Solution1 {
public:
    int findRadius(vector<int>& houses, vector<int>& heaters) {
        int m = houses.size();
        int n = heaters.size();
        int j{0};
        int res{0};
        sort(houses.begin(), houses.end());
        sort(heaters.begin(), heaters.end());
        for (int i{0}; i < m; ++i) { // 遍历房子
            int cur = houses[i];
            while (j < n-1 && abs(heaters[j+1] - cur) <= abs(heaters[j] - cur))
                ++j;
            res = max(res, abs(heaters[j] - cur));
        }
        return res;
    }
};

#include "../stdc++.h"

// 排序 + 二分查找
class Solution {
public:
    int findRadius(vector<int>& houses, vector<int>& heaters) {
        int res{0};
        sort(heaters.begin(), heaters.end());
        for (int& house : houses) {
            int j = upper_bound(heaters.begin(), heaters.end(), house) - heaters.begin();
            int i = j - 1;
            int rightDistance = j >= heaters.size() ? INT_MAX : heaters[j] - house;
            int leftDistance = i < 0 ? INT_MAX : house - heaters[i];
            int curDistance = min(leftDistance, rightDistance);
            res = max(res, curDistance);
        }
        return res;
    }
};

// 排序 + 双指针
class Solution {
public:
    int findRadius(vector<int>& houses, vector<int>& heaters) {
        sort(houses.begin(), houses.end());
        sort(heaters.begin(), heaters.end());
        int res{0};
        int m = houses.size();
        int n = heaters.size();
        for (int i{0}, j{0}; i < m; ++i) {
            int curDistance = abs(houses[i] - heaters[j]);
            while (j < n - 1 && abs(houses[i] - heaters[j]) >= abs(houses[i] - heaters[j + 1])) {
                ++j;
                curDistance = min(curDistance, abs(houses[i] - heaters[j]));
            }
            res = max(res, curDistance);
        }
        return res;
    }
};
